The field of computer graphics concerns the creation, storage, manipulation, and display of pictures and models of objects by a digital processor. Interactive computer graphics is generally a subclassification in the field of computer graphics in which a user dynamically controls the picture's content, format, size, or color on a display surface by means of an interaction device, such as a keyboard, lever, or joystick. The creation of synthetic images (i.e., images which exist as abstract collections of lines, points, curves, etc. in the computer's memory) is the usual domain of interactive computer graphics.
There are two primary classes of interactive computer graphics systems: random-scan and raster-scan systems. Images displayed by a random-scan system are encoded as commands to draw each output primitive (i.e., point, line or polygon) by plotting individual points or drawing connecting lines between specified starting and ending coordinates of line segments. Polygons are simply treated as a closed series of line segments. Encoding for a raster-scan system is much simpler: output primitives are broken up into their constituent points for display. The major difference between a simple point-plotting random-scan system and a raster-scan system is in the organization of the stored data used to drive the display. As explained below, the data is stored in a "frame buffer" (also called a "refresh buffer").
In the random-scan system, the component points of each successive output primitive are stored sequentially in memory and are plotted in that order, one point at a time. This is because the beam may be moved randomly on the screen. In the raster-scan system, the refresh memory is arranged as a 2-dimensional array of data. The value stored at a particular row and column encodes an intensity and/or color value of a corresponding display element on the screen. By convention, the location of each display element is specified by a unique (X,Y) coordinate. Since each memory location defines a single point-sized element of an image, both the display screen location and its corresponding memory location are often called a "pixel," short for the image processing term "picture element."
The overall speed with which all or part of the stored image data can be changed is dependent upon, among other things, how fast the image creation system executes instructions. It is the image creation system's execution of instructions which is often the slowest process in creating or changing an image. This is because the "scan conversion" algorithm, which is described in more detail in the next paragraph, typically requires many iterations. Usually, the faster the scan conversion algorithm, the faster the overall system response time to user commands. In addition, it is known that response time is critical to user satisfaction and, perhaps more importantly, to user productivity.
The process of converting a line, point, and area representation of an image to the array of pixel data in the image storage system is called "scan conversion." Scan conversion algorithms are always needed in an interactive raster-scan graphics system and are usually incorporated into the image creation system. The scan conversion algorithm used in a raster-scan graphics system will be invoked quite often, typically thousands of times, each time an image is created or modified. Hence, it must not only create visually pleasing images, but must also execute as rapidly as possible. Indeed, speed versus image quality is the basic tradeoff in known scan conversion algorithms. Some scan conversion algorithms are fast and give jagged edges, while others are slower but give smoother edges. Edges that are jagged as a result of transformation into pixels are often referred to as "aliased", and further, the process of smoothing jagged edges is commonly referred to as "antialiasing."
The problem of antialiasing has been studied since the mid 1970's, when Frank Crow wrote about the problem. Crow identified three problem areas that give rise to aliasing in computer generated images. These three problem areas are as follows: edges on the silhouettes of objects, very small objects (subpixel), and areas of complicated detail (many subpixel parts of objects within a single pixel). It is interesting to note that the silhouette edges of polygons are where most people notice the aliasing problem. In fact, some people have considered the aliasing problem as only the silhouette edge problem. This has lead to some very bad solutions to the problem. The most notable of these solutions is to draw antialiased vectors around the edges of polygons. This concept falls apart as one starts to work with subpixel geometry and in complex regions of an image.
Alpha blending has been used to antialias images. The idea behind alpha blending is to find the percent coverage of a pixel by a polygon and then use that information to blend the new data into the background. The primary problem is that the data must be sorted in the depth dimension (z direction) of the screen space viewing cube. This is because at each pixel the frame buffer saves only the color information (i.e. no z data is saved). As an example of the need for z sorting, consider a pixel that is totally covered by part of a green polygon. Next, assume an edge of a red polygon is drawn in the same pixel, where only 50% of the pixel is covered. In that case the resultant pixel color will be computed as follows: EQU red(0.5)+((1.0 green)(1.0-0.5))=0.5 red+0.5 green
This blend of red and green will be a good aesthetically pleasing mix if the red polygon is in front of the green one. If the green one is in front, then the red showing through will result in an incorrect appearance.
If the red is behind the green polygon, then the red should be drawn first resulting in a 50% red pixel. Next, the 100% green polygon should be drawn resulting in the following correct blend: EQU green (1.0)+((0.5 red) (1.0-1.0))=1.0 green+0.0 red
For a typical application, the requirement that the data be transformed to screen space and then sorted is unreasonable. It is also important to note that, even with the data sorted in screen space, there are artifacts that occur when as few as two polygons share a common pixel. In other words, the alpha blending method does not handle regions of complicated detail.
Another known method for antialiasing is the accumulation buffer method. In principle, the accumulation buffer method can antialias any image. The idea is to render the image several times, where each time a different subpixel sampling grid is used. The results of several passes through the rendering are then combined to produce the final image. Dedicated hardware for use as an accumulation buffer has been discussed since the mid 1980's.
There are several features that make the accumulation buffer method attractive. One of the best features of this method is that images of very high quality can be produced. For example, images can be produced with 64 subsamples per pixel. In addition to antialiasing, the use of accumulation buffers works well to produce other sophisticated effects, such as motion blur and depth of field.
There are two primary disadvantages to the accumulation buffer method. First, performance is noticeably affected when antialiasing is enabled. Second, application programs need to be modified to take advantage of the method.
The first disadvantage can be explained as follows. In order to use an accumulation buffer, the database must be transformed and rendered several times. In addition, the final image must be assembled after the process is completed. So, an image with 4 subsamples per pixel will take about 5 times as long to render antialiased as compared to aliased. This performance problem can be alleviated with the use of progressive refinement. When using progressive refinement, the resultant image is displayed after each rendering pass. The net effect is that the image "appears" as getting progressively better. However, this changing image can be distracting to interactive work.
As for the second disadvantage of the accumulation buffer method, application programs must be changed to take advantage of the antialiasing. The application must resend the data through the transform and rendering process for each pass. In addition, the application needs to know what to do when the user wishes to change the view before all the passes through the data are complete. Up to this point in time, application writers have been unwilling to make these changes.
Still another known method for antialiasing is the multipoint sampling method. The multipoint sampling method allows each pixel to be sampled several times. The idea is to sample at several subpixel locations within each pixel. These samples are referred to herein as "subsamples." In this regard, it is similar to the accumulation buffer method. However, when using the multipoint sampling method, the data is transformed and sent to the rendering pipeline only once. The rendering hardware then uses the subpixel location data associated with each primitive to sample it at several subpixel locations at once.
The biggest advantage of the multipoint sampling method is that the application programs do not need to change. Other advantages are based on the fact that image data must be passed to the rendering hardware only one time. These advantages include: (1) the host processor does not do additional work to antialias the image; (2) the bus bandwidth required between the host and the graphics system is not affected by antialiasing; and (3) the transformation and lighting parts of the graphics pipeline are unaffected.
One of the disadvantages with the multipoint sampling method is that the image quality may not be as good as with the accumulation buffer method. This is because the multipoint sampling method requires storage (i.e. additional random access memory; RAM) for each subsample color and depth. Therefore, the number of subsamples per pixel is fixed by the hardware. For example, consider the "REALITYENGINE,".TM. which is manufactured by and commercially available from Silicon Graphics Computer Systems, U.S.A. There is a limit of 4 subsamples per pixel in the high resolution mode (1280.times.1024) on this system with a single raster board. In order to increase the number of subsamples to 16 per pixel the user is forced to move to a four raster board Reality Engine. In contrast, when using an accumulation buffer, there is essentially no limit on the number of sampling passes possible. Of course, there is a performance penalty for increasing the number of passes through the data. The additional subsamples used with the accumulation buffer result in a higher quality image.
The next disadvantage is performance. Although the front end of the graphics pipeline is unaffected by use of the multipoint sampling method for polygon antialiasing, the scan conversion hardware must process all of the subsamples in parallel or else the scan converter may be the bottleneck. For example, when a single subsample requires the displayed image to change at a pixel location, then the multipoint method requires combining the data from all of the subsamples in order to produce the new display color. In traditional systems, this means that the scan converter must read all of the color data for the unchanging subsamples and the z data for the changing subsample. The scan converter must generate the new color and write the display color, the new color, and z values for the changed subsample. This undesirably requires far more data manipulation and memory accesses than conventional aliased display systems, and results in a significant performance penalty.
Possibly the biggest disadvantage of using the multipoint sampling method is the additional hardware cost. As stated above, each subsample requires storage. In addition, there is extra logic in the scan converter chips. However, the cost delta is dominated by the extra frame buffer storage. For example, a 1280.times.1024 display with 4 true color subsamples per pixel requires about 20 megabytes of additional frame buffer memory. This translates into a large factory cost.